# @Time    :2025/4/15 11:39
"""时间复杂度nlongn"""
def merge(left_sort, right_sort):
    """合并"""
    mer = []  # 定义一个空数组，用来放排序后的元素
    i, j = 0, 0  # i 指向在left_sort的第一个元素
    while len(left_sort) > i and len(right_sort) > j:
        if left_sort[i] > right_sort[j]:
            mer.append(right_sort[j])
            j += 1
        else:
            mer.append(left_sort[i])
            i += 1
    # 将数组中剩余的元素增加到新数组里
    mer.extend(left_sort[i:])
    mer.extend(right_sort[j:])
    return mer


def merge_sort(arrs):
    """拆分数组"""
    if len(arrs) <= 1:
        return arrs

    mid = len(arrs) // 2
    left_sort = merge_sort(arrs[:mid])
    right_sort = merge_sort(arrs[mid:])

    return merge(left_sort, right_sort)


list1 = [2, 4, 7, 5]
print(merge_sort(list1))
